1. Field of the Invention
The present invention relates to a parallel multiplier, and more particularly, to an apparatus and method for digital multiplication adopting a redundant binary arithmetic technique to generate a partial product.
2. Description of the Related Art
With a recent trend toward system-on-a-chip (SoC), the functional blocks to constituting an integrated circuit are being demanded to occupy a small area of hardware while having improved performances. A multiplier is representative of the functional blocks, and plays an important role in many high-performance microprocessors or signal processing chips. Hence, a technique of reducing the size of a multiplier while maintaining the performance thereof is required to conform with the SoC trend.
In a multiplication arithmetic algorithm used in conventional multipliers, partial products are obtained using a modified booth""s algorithm (MBA) and are added by a carry-save adder having a structure such as a Wallace-tree, to thereby obtain a final multiplication result. This multiplication is usually achieved using normal binary arithmetic. Here, the partial products can be summed using a redundant binary arithmetic technique instead of normal binary arithmetic technique. The characteristic of redundant binary arithmetic is that there is no continuous propagation of carry as required by general arithmetic for summing partial products.
A conventional arithmetic method performed by a multiplier using a redundant binary arithmetic will now be described. In this method, first, partial products are produced from input values by a normal binary arithmetic operation using an MBA.
A conventional multiplication method using the above-described MBA uses a radix-4 numeration system. That is, when numbers X and Y are multiplied, the number Y having m bits is expressed as in Equation 1 according to the MBA:                     Y        =                              ∑                          i              -              0                                                      m                2                            -              1                                ⁢                                    D              i                        ·                          4              i                                                          (        1        )            
wherein Di corresponds to one among a group of values xe2x88x922, xe2x88x921, 0, 1 and 2, and is obtained by encoding three consecutive bits Yi+2, yi+1 and yi of the number Y by a calculation of xe2x88x922xc2x7yi+2+yi+1+yi. Every three consecutive bits of the m bits of number Y are grouped and consecutive groups overlap by one bit such that the last bit of each group is the first bit of the following group, thus   ⌈      m    2    ⌉
3-bit groups are obtained, and thus the number m of partial products is reduced to       ⌈                  m        2            +      1        ⌉    .
Here, ┌x┐ denotes the smallest integer among integers that are greater than x. The reason why +1 is added is that correction bits to be added to the least significant bit of each of the partial products due to the 2""s complement arithmetic are collected and the collected result is considered as a single partial product. The method of grouping three bits to encode m-bit Y in the MBA system is illustrated in Equation 2:                                                         y                              m                -                1                                      ⁢                          xe2x80x83                                            ⏟                          D                                                m                  2                                -                                  1                  ⁢                  …                                                                    ⁢        …        ⁢                  xe2x80x83                ⁢                                                            y                                  1                  -                  1                                                            ⏞                                  …                  ⁢                                      xe2x80x83                                    ⁢                                      D                                          1                      2                                                                                            ⁢                          y                              1                -                2                                      ⁢                                          y                                  1                  -                  3                                                            ⏞                                  D                                                            1                      2                                        -                    2                                                                                            ⏟                          D                                                1                  2                                -                                  1                  ⁢                  …                                                                    ⁢                  xe2x80x83                ⁢        …        ⁢                  xe2x80x83                ⁢                  y          2                ⁢                  xe2x80x83                ⁢                                                                              y                  1                                ⁢                                  y                  0                                                            ⏟                                  D                  1                                                      ⁢                          xe2x80x83                        ⁢            0                                ⏞                          …              ⁢                              xe2x80x83                            ⁢                              D                0                                                                        (        2        )            
Equation 2 is applied when m is an even number, and always adds xe2x80x980xe2x80x99 next to the least significant bit. In this case, since the MBA performs encoding using a radix-4, every three consecutive bits of the m bits of number Y are grouped and consecutive groups overlap by one bit such that the last bit of each group is the first bit of the following group, as shown in Equation 2. In a general case where the m-bit number Y is encoded in a 2k radix numeration system, every k+1 consecutive bits of the m bits of number Y are grouped and consecutive groups overlap by one bit such that the last bit of each group is the first bit of the following group. Here, partial products formed in normal binary numbers are produced by multiplying Di by X.
Next, the partial products formed in normal binary numbers are converted into partial products expressed in redundant binary numbers. That is, the sum of partial products A and B formed in normal binary numbers can be expressed as in Equation 3:
A+B=Axe2x88x92(xe2x88x92B)=Axe2x88x92({overscore (B)}+1)=(Axe2x88x92{overscore (B)})xe2x88x921xe2x80x83xe2x80x83(3)
Here, if axe2x88x92b is defined to be (a,b), it can be seen from Equation 4 that xe2x88x921 is equal to (0,1):
Axe2x88x92{overscore (B)}xe2x89xa1(A,{overscore (B)})xe2x80x83xe2x80x83(4)
wherein the right side represents the redundant binary number of the result of A+B arithmetic operation. In the right side of Equation 3, xe2x88x921, which is finally added to the least significant bit, is a correction bit to be added by the 2""s complement arithmetic operation. Here, xe2x88x921 can be expressed in a redundant binary number (0,1). When Equation 3 is adopted in the addition of partial products formed in normal binary numbers, the sum of partial products formed in redundant binary numbers can be obtained by pairing many normal binary partial products and inverting one of two normal binary partial products.
Consequently, when m-bit multiplication input values are multiplied by the MBA,       ⌈          m      2        ⌉    +  1
normal binary partial products are produced. Thus, r normal binary partial products are once summed while being converted into redundant binary numbers, resulting in the   ⌈      r    2    ⌉
sum expressed in redundant binary numbers.
These redundant binary numbers are summed by a redundant binary arithmetic operation on the basis of an addition rule as shown in Table 1, thereby obtaining the final product of X and Y, the product appearing in a redundant binary form.
Table 1 denotes a rule of summing redundant binary numbers using a conventional arithmatic technique. In Table 1, (ai+,aixe2x88x92) and (bi+,bixe2x88x92) denote two redundant binary numbers intended to be added, (ci+,cixe2x88x92) and (si+,sixe2x88x92) represent an intermediate carry and an intermediate sum, respectively, which are expressed in redundant binary numbers, when two numbers are added, and xe2x80x9ceitherxe2x80x9d denotes that it does not matter whether xe2x80x980xe2x80x99 or xe2x80x981xe2x80x99 is selected as h1xe2x88x921. Also, hixe2x88x921 denotes an intermediate parameter made to prevent continuous carry propagation. Values of (ai+,aixe2x88x92) and (bi+,bixe2x88x92) when hi is 1 are bolded values. In the case of hi=1, value xe2x88x921 can be possibly propagated as a carry.
Referring to Table 1, an addition of two redundant binary numbers [(ai+,aixe2x88x92) and (bi+,bixe2x88x92)] corresponds to one among the five cases described above.
In Case 1 that the sum of two redundant binary numbers is zero, both the intermediate carry and the intermediate sum are 0. In Case 2 that the sum of two redundant binary numbers is xe2x88x921, if there is a possibility that xe2x88x921 is propagated from the next lower digit, that is, if hi is 1, the intermediate sum and the intermediate carry are 1 and xe2x88x921, respectively, so that xe2x88x921 is offset by the intermediate sum of 1 even if xe2x88x921 is propagated. Thus, the addition can be carried out without carry propagation. In Case 3 that the sum of two redundant binary numbers is 1, if there is a possibility that 1 is propagated from the next lower digit, that is, if hi is 0, the intermediate sum and the intermediate carry are xe2x88x921 and 1, respectively, so that 1 is offset by the intermediate sum of xe2x88x921 even if 1 is propagated. Thus, the addition can be carried out without carry propagation. In Case 3, if hi is 1, there is a possibility that xe2x88x921 is propagated from the next lower digit, so that the intermediate sum and the intermediate carry are 1 and 0, respectively. Thus, the value xe2x88x921 is offset by the intermediate sum of 1 even if xe2x88x921 is propagated, so that there is no further propagation of carry. In Case 4 that the sum of two redundant binary numbers is xe2x88x922, and Case 5 that the sum is 2, there is no further propagation of carry, and the intermediate sum is 0, regardless of the value of carry to be propagated from the next lower digit. The intermediate carry for Case 4 is xe2x88x921, and the intermediate carry for Case 5 is 1. When two redundant binary numbers are summed as shown in Table 1, a case that both (ai+,aixe2x88x92) and (bi+,bixe2x88x92) take the state (1,1) is excluded on the assumption that (1,1) has already been transformed to (0,0). The final sum (di+,dixe2x88x92) of two redundant binary numbers according to the rule shown in Table 1 can be expressed as in Equation 5:
di+=(si++cixe2x88x921+)xc2x7{overscore ((sixe2x88x92+cixe2x88x921xe2x88x92))}, dixe2x88x92={overscore ((si++cixe2x88x921+))}xc2x7(sixe2x88x92+cixe2x88x921xe2x88x92),
di+={overscore ((li⊕hixe2x88x921))}xc2x7({overscore (lixe2x88x921)}xc2x7kixe2x88x921+lixe2x88x921xc2x7{overscore (hixe2x88x922)}) 
dixe2x88x92=(li⊕hixe2x88x921)xc2x7{overscore ((lixe2x88x921)}xc2x7kixe2x88x921+lixe2x88x921xc2x7{overscore (hixe2x88x922)})
li=(ai+aixe2x88x92)⊕(bi+bixe2x88x92), hi=aixe2x88x92+bixe2x88x92, ki=ai++bi+xe2x80x83xe2x80x83(5)
if the radix of a number system used increases, the number of partial products further decreases. In general, when an 2k radix is used, the number of partial products decreases to       ⌈          m      2        ⌉    +  1.
In the case of the multiplication of m-bit numbers X and Y using a 2k radix number system, the number Y is generally expressed as in Equation 6:                     Y        =                                            ∑                              i                =                0                                                              m                  k                                -                1                                      ⁢                                          D                i                            ·                              2                                  k                  ⁢                                      xe2x80x83                                    ⁢                  i                                                              =                                                    D                                                      m                    k                                    -                  1                                            ⁢                              D                                                      m                    k                                    -                  2                                            ⁢                              xe2x80x83                            ⁢              …              ⁢                              xe2x80x83                            ⁢                              D                i                            ⁢                              xe2x80x83                            ⁢              …              ⁢                              xe2x80x83                            ⁢                              D                1                            ⁢                              D                0                                      =            D                                              (        6        )            
wherein       D    i    =            y              ki        -        1              +          (                        ∑                      j            =            1                                k            -            1                          ⁢                              y                          ki              +              j              -              1                                ·                      2                          j              -              1                                          )        -                  y                              k            ⁡                          (                              i                +                1                            )                                -          1                    ·                        2                      k            -            1                          .            
In the case of a radix-4 MBA, Di by which X is multiplied is a value selected from a group of values {xe2x88x922, xe2x88x921, 0, 1, 2}, so that a partial product becomes one among values {xe2x88x922X, xe2x88x92X, 0, X, 2X}. The multiples of X can be simply obtained by left-shifting X, so that they place little burden on hardware. However, as the radix of a number system used increases, the burden on hardware increases. For example, in the case of a multiplication having a 2k radix, Di has a value selected from a group of values {xe2x88x922kxe2x88x921, xe2x88x922kxe2x88x921+1, . . . , 0, . . . , 2kxe2x88x921xe2x88x921, 2kxe2x88x921}. That is, the number of multiples of X that can be obtained by multiplying X by Di is 2k+1, and they are {xe2x88x922kxe2x88x921X, (xe2x88x922kxe2x88x921+1)X, . . . , 0X, . . . , (2kxe2x88x921xe2x88x921)X, 2kxe2x88x921X}. For example, in the case of a radix-64, k is 6, and a total of 65 multiples of X are required. A multiple of X such as 2iX among the multiples can be simply obtained by left-shifting X by i bits. However, odd multiples of X such as (2i+1)X cannot be obtained by the left-shifting operation. That is, in order to obtain 3X, a separate addition operation such as X+2X is required.
Consequently, when a multiplier using a redundant binary arithmetic performs a conventional arithmetic operation, the above-described separate arithmetic operation must be performed on each of the odd multiples of X. Therefore, the number of additional addition operations increases as the radix of a number system used for multiplication increases, so that a burden upon hardware increases.
To solve the above problem, an objective of the present invention is to provide a digital multiplication apparatus adopting a redundant binary arithmetic, by which the amount of hardware required can be reduced by applying the redundant binary arithmetic to produce partial products.
Another objective of the present invention is to provide a digital multiplication method performed by a digital multiplication apparatus adopting the redundant binary arithmetic.
To achieve the first objective, the present invention provides a digital multiplication apparatus adopting a redundant binary arithmetic for multiplying two numbers X and Y using a radix-2k number system, the apparatus including: a data converter for data converting the m-bit number Y into m/k-digit data D (=Dm/kxe2x88x921Dm/kxe2x88x922 . . . Di . . . DiDo); a partial product calculator for converting each of the digits Di of the number Y converted by the data converter into a combination of the coefficients of a fundamental multiple, multiplying the combination by the number X, and outputting the product as a redundant binary partial product; a redundant binary adder for summing the partial products for all of the digits of the converted number Y; and a redundant binary (RB)-normal binary (NB) converter for converting the redundant binary sum into a normal binary number and outputting the converted normal binary sum as the product of the two numbers.
To achieve the second objective, the present invention provides a digital multiplication method adopting a redundant binary arithmetic for multiplying two numbers X and Y using a radix-2k number system, the method including: (a) data-converting the m-bit number Y into m/k-digit data D (=Dm/kxe2x88x921Dm/kxe2x88x922 . . . Di . . . D1D0); (b) converting each of the digits Di of the number Y into a combination of the coefficients of a fundamental multiple, and multiplying the combination by the number X to obtain a redundant binary partial product; (c) summing the partial products for all of the digits of the number Y converted; and (d) converting the redundant binary sum into a normal binary number to obtain the product of the two numbers.